package cn.edu.xjtu.carlWay.tree.binaryTreePath;

import cn.edu.xjtu.Util.TreeNode.TreeNode;

import java.util.ArrayList;
import java.util.List;

/**
 * 257. 二叉树的所有路径
 * 给你一个二叉树的根节点 root ，按 任意顺序 ，返回所有从根节点到叶子节点的路径。
 * <p>
 * 叶子节点 是指没有子节点的节点。
 * <p>
 * https://leetcode-cn.com/problems/binary-tree-paths/
 */
public class Solution {
    public List<String> binaryTreePaths(TreeNode root) {
        if (root == null) {
            return null;
        }
        List<String> paths = new ArrayList<>();
        StringBuilder path = new StringBuilder();
        findPath(root, path, paths);
        return paths;
    }

    private void findPath(TreeNode node, StringBuilder path, List<String> paths) {
        if (node != null) {
            StringBuilder temp_path = new StringBuilder(path);
            temp_path.append(node.val);
            if (node.left == null && node.right == null) {
                paths.add(temp_path.toString());
            } else {
                temp_path.append("->");
                findPath(node.left, temp_path, paths);
                findPath(node.right, temp_path, paths);
            }
        }
    }
}
